package main

import "fmt"

// 快速排序：属于交换类排序——不稳定排序算法

// QuickSort 普通版本快速排序实现
func QuickSort(array []int, begin, end int) {
	if begin < end {
		// 进行切分
		loc := partition(array, begin, end)
		// 对左部分进行快排
		QuickSort(array, begin, loc - 1)
		// 对右部分进行快排
		QuickSort(array, loc + 1, end)
	}
}

// 切分函数，并返回切分元素的下标
func partition(array []int, begin int, end int) int {
	i := begin + 1	// 将array[begin]作为基准数，因此从array[begin + 1]开始与基准数进行比较
	j := end		// array[end]是数组最后一位

	// 没重合之前
	for i < j {
		if array[i] > array[begin] {
			array[i], array[j] = array[j], array[i]
			j--
		} else {
			i++
		}
	}

	// 跳出for循环后，i == j
	if array[i] >= array[begin] { // 这里必须要取等“>=”，否则数组元素由相同的值组成时，会出现错误！
		i--
	}

	array[begin], array[i] = array[i], array[begin]
	return i
}

// 算法改进：
// 在小规模数组的情况下，直接插入排序的效率最好，当快速排序递归部分进入小数组范围，可以切换成直接插入排序。
// 排序数列可能存在大量重复值，使用三向切分快速排序，将数组分成三部分，大于基准数，等于基准数，小于基准数，这个时候需要维护三个下标。
// 使用伪尾递归减少程序栈空间占用，使得栈空间复杂度从 O(logn) ~ log(n) 变为：O(logn)

func main() {
	list := []int{5}
	QuickSort(list, 0, len(list)-1)
	fmt.Println(list)
	list1 := []int{5, 9}
	QuickSort(list1, 0, len(list1)-1)
	fmt.Println(list1)
	list2 := []int{5, 9, 1}
	QuickSort(list2, 0, len(list2)-1)
	fmt.Println(list2)
	list3 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	QuickSort(list3, 0, len(list3)-1)
	fmt.Println(list3)

}



























